Optimisasi Konveks: Kondisi Optimal untuk Kendala Persamaan

Bayangkan sistem fisik, seperti rantai yang menggantung, yang mencari keadaan energi terendah. Jika ujung-ujungnya tetap, sistem tidak dapat bergerak bebas. Optimalitas tercapai ketika gaya internal (gradien energi potensial) seimbang sempurna dengan gaya tegangan yang dihasilkan oleh kendala. Dalam optimisasi konveks, keseimbangan ini ditangkap oleh kondisi KKT untuk kendala persamaan.

Geometri Feasibilitas

Untuk masalah konveks dengan kendala persamaan $Ax=b$, vektor $v \in \mathbf{R}^n$ adalah arah layak jika $Av = 0$. Ini berarti bahwa bergerak dalam arah $v$ mempertahankan kendala: $A(x+v) = b$ jika $Ax=b$.

Agar $x^*$ optimal, turunan arah $\nabla f(x^*)^T v$ harus nol untuk semua arah layak $v$ dalam ruang nol $\mathcal{N}(A)$. Ini menyiratkan bahwa gradien $\nabla f(x^*)$ harus ortogonal terhadap $\mathcal{N}(A)$, yang membawa kita pada eksistensi pengali Lagrange.

Kondisi Optimalitas

Suatu titik $x^*$ optimal jika dan hanya jika terdapat vektor $\nu^* \in \mathbb{R}^p$ sedemikian sehingga:

$\nabla f(x^*) + A^T \nu^* = 0$

Ini membentuk sistem persamaan linear yang menggambarkan keseimbangan antara penurunan fungsi objektif dan manifold kendala.

Gradien Terproyeksi

Proyeksi proyeksi Euclidean dari gradien negatif $-\nabla f(x)$ ke ruang nol $\mathcal{N}(A)$ diberikan oleh:

$\Delta x_{\text{pg}} = \text{argmin}_{Au=0} \| -\nabla f(x) - u \|_2$

Vektor ini merepresentasikan arah penurunan layak yang "terbaik". Sangat penting, $x$ optimal jika dan hanya jika $\Delta x_{\text{pg}} = 0$.

Sistem KKT dan Sifat Matriks

Kita dapat menyelesaikan langkah Newton dan variabel dual secara bersamaan menggunakan sistem blok:

$$\begin{bmatrix} I & A^T \\ A & 0 \end{bmatrix} \begin{bmatrix} v \\ w \end{bmatrix} = \begin{bmatrix} -\nabla f(x) \\ 0 \end{bmatrix}$$

Catatan tentang Sifat Spektral Matriks: Matriks KKT bersifat simetris tetapi tidak definit. Jika matriks tersebut tak singular, maka memiliki tepat $n$ nilai eigen positif dan $p$ nilai eigen negatif. Ini menyiratkan bahwa titik optimal $(x^*, \nu^*)$ merupakan titik sadel dari Lagrangian $L(x, \nu) = f(x) + \nu^T(Ax-b)$, bukan titik minimum lokal sederhana dalam ruang primal-dua yang digabungkan.

🎯 Prinsip Utama

Optimalitas dalam masalah dengan kendala persamaan mengharuskan gradien menjadi ortogonal terhadap ruang nol kendala. Ini memungkinkan kita menginterpretasikan langkah Newton sebagai solusi dari pendekatan linearisasi kondisi KKT.

PERTANYAAN 1

Apa yang mendefinisikan 'arah layak' $v$ di suatu titik $x$ untuk kendala $Ax = b$?

$Av = b$

$Av = 0$

$\|v\|_2 = 1$

$A^T v = 0$

PERTANYAAN 2

Apa interpretasi fisik dari kondisi $\nabla f(x^*) + A^T \nu^* = 0$?

Gradien bernilai nol di semua arah.

Fungsi objektif telah mencapai minimum global tanpa kendala.

Gaya internal ('gaya') (gradien) seimbang dengan 'tegangan' dari kendala.

Semua pengali Lagrange harus positif.

PERTANYAAN 3

Jika matriks KKT tidak singular, apa tanda nilai eigennya?

Semua $n+p$ nilai eigen positif.

$n$ nilai eigen positif dan $p$ nilai eigen negatif.

$p$ nilai eigen positif dan $n$ nilai eigen negatif.

Semua nilai eigen real dan tak nol, tetapi tandanya tergantung pada $f(x)$.

PERTANYAAN 4

Gradien terproyeksi $\Delta x_{\text{pg}}$ bernilai nol jika dan hanya jika:

Gradien $\nabla f(x)$ bernilai nol.

Titik $x$ berada di ruang nol $A$.

Titik $x$ memenuhi kondisi optimalitas orde pertama.

Matriks $A$ berbentuk persegi dan dapat dibalik.

PERTANYAAN 5

Dalam sistem $\begin{bmatrix} I & A^T \\ A & 0 \end{bmatrix} \begin{bmatrix} v \\ w \end{bmatrix} = \begin{bmatrix} -\nabla f(x) \\ 0 \end{bmatrix}$, apa yang diwakili oleh $v$?

Solusi optimal $x^*$.

Vektor pengali Lagrange.

Gradien terproyeksi $\Delta x_{\text{pg}}$.

Residual primal $Ax - b$.